Data communications based on computer technology and communication technology have become in recent years widely in use. In these data communications, a privacy communication system and a digital signature system are used. Here, the privacy communication system is a system in which communication is performed with the communication contents kept secret from any other entities except for certain communication destinations. The digital signature system is a communication system showing the validity of the communication contents to the communication destinations, or proving the sender's identity.
1. Public Key Encryption System
An encryption system called a public key encryption system is used in the privacy communication system or the digital signature system. In the privacy communications using the public key encryption system, the encryption key and the decryption key are different from each other, and the encryption key is made publicly available while the decryption key being kept secret. The decryption key kept secret is called a private key, and the encryption key made publicly available is called a public key. When there are a number of communication destinations, a key must be kept between the communication destinations in common key encryption. On the other hand, in public key encryption, communications are made possible if the communication destinations simply have a single unique key, and therefore, the number of keys required is less than in the common key encryption even if the number of communication destinations increases. Thus, the public key encryption is well suited to communications with a number of destinations, and indispensable and fundamental technology.
The safety of an RSA encryption system—a type of the public key encryption system—is based on that solving prime factorization of integers is difficult in terms of computational effort. The prime factorization is a problem to find primes p and q with respect to an integer n, when n=p×q. Here, “×” is general multiplication. In general, when p and q are as large, for example, as 1024 bits, solving the prime factorization is difficult. This therefore makes it difficult to find out a private key from a public key with the RSA encryption system, and also makes it difficult for users not having the private key to find out a plain text from an encrypted text. Note that prime factorization is discussed in detail in Non-Patent Reference 1 (pp. 144-151).
1.1 RSA Encryption System Applying Prime Factorization
Here is described the RSA encryption system applying prime factorization.
(1) Key Generation
A public key and a private key are calculated in the following manner:                Choose large primes p and q randomly, and calculate the multiplication n=p×q;        Calculate the least common multiple L=LCM(p−1, q−1) of (p−1) and (q−1);        Choose randomly a natural number e which is coprime to L and is smaller than L,1≦e≦L−1, GCD(e, L)=1,where “GCD(e, L)” is the greatest common divisor of e and L; and        Calculate d satisfying e×d=1 mod L.Since GCD(e, L)=1, such d exists without exception. The integers e and n obtained thus form a public key while the integer d is a private key. Here, “x mod y” is a reminder when x is divided by y.        
(2) Generation of Encrypted Text
By using the integers e and n of the public key, an encrypted text c is calculated by performing encryption calculation on a plain text m.c=m^e mod n
Note that, in this description, an operator “^” indicates that a number following this is an exponent. For example, “A^x” means A is multiplied by itself x times when x>0.
(3) Generation of Decrypted Text
By using the integer number d of the private key, a decrypted text m′ is calculated by performing decryption calculation on the encrypted text c.m′=c^d mod n
Note that the decrypted text m′ agrees with the plain text m since
                              m          ′                =                              c            ^            d                    ⁢                                          ⁢          mod          ⁢                                          ⁢          n                                        =                                            (                              m                ^                ⅇ                            )                        ^            d                    ⁢                                          ⁢          mod          ⁢                                          ⁢          n                                        =                              m            ^                          (                              ⅇ                ×                d                ⁢                                                                  ⁢                                  mod                  ⁢                  L                                            ⁢                                                          )                                ⁢          mod          ⁢                                          ⁢          n                                        =                              m            ^            1                    ⁢                                          ⁢          mod          ⁢                                          ⁢          n                                        =                  m          ⁢                                          ⁢          mod          ⁢                                          ⁢                      n            .                              
RSA encryption is discussed in detail in Non-Patent Reference 2 (pp. 110-113).
The generation of primes is carries out in the public key generation step in the RSA encryption applying the prime factorization described above. The prime generation is described in detail in Non-Patent Reference 3 (pp. 145-154). There are two types of methods to generate primes: stochastic prime generation methods and deterministic prime generation methods. Primes generated by a stochastic prime generation method are numbers “likely to be primes”, and they are not always primes. On the other hand, a deterministic prime generation method unfailingly generates primes. Details of stochastic and deterministic prime generation methods are described in Non-Patent Reference 2. The following gives an account of a deterministic prime generation method.
1.2 Example of Conventional Technique 1: Deterministic Prime Generation Method
Here is described a deterministic prime generation method using Maurer's method, by which primes are deterministically generated. The Maurer method is discussed in detail in Non-Patent Reference 3 (pp. 152-153).
In the deterministic prime generation method, primes are generated by repeating the following steps. A prime q having a bit size lenq is provided in advance.
<Step 1> A random number R having (lenq−1) bits is selected. Note that the beginning bit of the random number R must never fail to be 1.
<Step 2> A number N is calculated by using the following equation:N=2×q×R+1.
<Step 3> When the following 1st and 2nd judgments are both true, the number N is determined as a prime. Otherwise, it is determined as not being a prime.
1st judgment: 2^(N−1)=1 mod N; and
2nd judgment: GCD (2^(2R)−1, N)=1.
When being determined as a prime, the number N is output as a prime. When the number N is determined as not being a prime, the processing returns to Step 1 and is repeated until a prime is output.
The judging test of Step 3 is called the Pocklington's primality test, and described in detail in Non-Patent Reference 3 (p. 144). In the Pocklington's primality test, when q in “N=2×q×R+1” is a prime and the results of the 1st and 2nd judgments are true, the number N is unfailingly a prime. Therefore, it makes possible to determine and generate a prime in a deterministic manner.
In the deterministic prime generation using the Maurer's method, the prime N having a size 2×lenq is thus generated based on the prime q having a size lenq. Accordingly, in the case when a prime having a predetermined length is to be generated by using the Maurer's deterministic prime generation method, the generation of a prime having a length shorter than or the same as the predetermined length is repeated. For example, when a 512-bit length prime is to be generated, a 16-bit prime is generated based on an 8-bit prime provided in advance. Then, a 32-bit prime is generated based on the generated 16-bit prime. Next a 64-bit prime is generated based on the generated 32-bit prime. After the repetition of the prime generation in a similar fashion, a 512-bit prime is generated.
Note that the 2nd judgment can be replaced by the following judgment.
3rd judgment: 2^(2R)≠1 mod N
The 3rd judgment is discussed in Non-Patent Reference 4. Hereinafter, the 3rd judgment is employed.
1.3 Key Issuing System Having Multiple Key Issuing Servers
Regarding key issuing systems for public key encryption, there are cases where a key is generated by a user and where a key is issued to a user by a key issuing server. When a key is issued by a key issuing server, it is often the case that a single server issues a key to the user. However, in order to reduce the processing load, a key issuing system may have multiple key management servers, and keys are issued by the respective key management servers.
<Patent Reference 1> Japanese Laid-Open Patent Application Publication No. 2003-5644;
<Non-Patent Reference 1> Coedited by Tatsuaki Okamoto and Kazuo Ohta, Angou • Zero Chishiki Mondai • Suron (Encryption • Zero Knowledge Problems • Number Theory), 1990, Kyoritsu Syuppan;
<Non-Patent Reference 2> Tatsuaki Okamoto and Hiroshi Yamamoto, Gendai Angou (Modern Encryption), 1997, Sangyo-Tosho;
<Non-Patent Reference 3> A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography, 1997, CRC Press;
<Non-Patent Reference 4> Eiji Okamoto, Angou Riron Nyumon (Introduction to Encryption Theory), 1993, p. 21, Kyoritsu Syuppan; and
<Non-Patent Reference 5> Henri Cohen, A Course in Computational Algebraic Number Theory, 1993, GTM 138, Springer-Verlag.